package String;

public class LongestCommanPrePostfix {
    /**
     * KMP中的最长公共前后缀数组，数组中存的值意义为：
     * i位置（不包括i）之前的最长公共前后缀的长度
     * @param s
     * @return 返回的是最长公共前后缀数组
     */
    public int[] getPrePostfix(String s){
        int res[] = new int[s.length()+1];
        if(s.length() == 1){
            return res;
        }
        res[0] = -1;
        res[1] = 0;
        for (int i = 2; i <= s.length(); ++i) {
            int jump = res[i-1];
            while (jump != -1 && s.charAt(jump) != s.charAt(i - 1)) {
                jump = res[jump];
            }
            res[i] = jump + 1;
        }
        return res;
    }
}
